130. Surrounded Regions

Medium

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically

首先这题让我想到了数海岛那道题，同样都需要找联通的图案，所以很自然就想到需要dfs来进行联通的遍历，但是由于dfs必然会重复遍历一些点，所以就需要visit来记录哪些点已经遍历过了。

首先，根据观察可以发现，只有边上的O或者是和边上O连起来的O才不会被变成X。所以我的思路很简单，就是遍历除边上以外的O，再通过dfs查找他是否于边上的O连着。但是时间复杂度一想就很高。

然后我想到利用visit在dfs的过程中就标记好联通的O然后一起改成X，这部分代码暂定

最后看了别人的思路。感觉很有道理。

解法一是从当前节点做 DFS ，然后看它是否能到达边界的 O。那么我们能不能把思路逆转过来呢？从边界的 O 做 DFS，然后把遇到的 O 都标记一下，这些 O 就是可以连通到边界的。然后把边界的所有的 O 都做一次 DFS ，把 DFS 过程的中的 O 做一下标记。最后我们只需要遍历节点，把没有标记过的 O 改成 X 就可以了。标记的话，我们可以用一个 visited 二维数组，把访问过的置为 true 。

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board: return
        r = len(board)
        c = len(board[0])
        visit = [[False]*c for i in range(r)] # record if this spot has been visited
        for i in range(0, r):
            for j in range(0, c):
                if (i == 0 or i == r-1 or j == 0 or j == c-1):
                    if board[i][j] == 'O' and not visit[i][j]:
                        self.dfs(i, j, visit, board)
        for i in range(0, r):
            for j in range(0, c):
                if not visit[i][j] and board[i][j] == 'O':
                    board[i][j] = 'X'
                        
                    
    def dfs(self, i, j, visit, board):
        if (i<len(board) and i>=0 and j<len(board[0]) and j>=0):
            if board[i][j] == "O" and not visit[i][j]: 
              # notic here, without not visit, we can not reach to the recursion end
                visit[i][j] = True
                self.dfs(i+1,j,visit,board)
                self.dfs(i,j+1,visit,board)
                self.dfs(i-1,j,visit,board)
                self.dfs(i,j-1,visit,board)
                return
            else: # == "X"
                return
        else: return

同样参考了他的优化改良思路。直接在board上记录，不需要visit

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board: return
        r = len(board)
        c = len(board[0])
        for i in range(0, r):
            for j in range(0, c):
                if (i == 0 or i == r-1 or j == 0 or j == c-1):
                    if board[i][j] == 'O':
                        self.dfs(i, j, board)
        for i in range(0, r):
            for j in range(0, c):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                if board[i][j] == '*':
                    board[i][j] = 'O'
                    
    def dfs(self, i, j, board):
        if (i<len(board) and i>=0 and j<len(board[0]) and j>=0):
            if board[i][j] == "O" :
                board[i][j] = '*'
                self.dfs(i+1,j,board)
                self.dfs(i,j+1,board)
                self.dfs(i-1,j,board)
                self.dfs(i,j-1,board)
                return
            else: # == "X"
                return
        else: return

2. UnionFind 查并集

   查并集是什么，可以点这里。虽然查并集用在这题效率并没有高多少，但是这也不失为一种简单，且容易想到的解题思路。

   查并集，算法如其名，两大功能就是查找（found）和合并（Union）。

class UnionFound:
    def __init__(self, totalNode):
        self.parents = []
        for i in range(totalNode):
            self.parents.append(i)
    def find(self, node:int):
        while(self.parents[node] != node):
            self.parents[node] = self.parents[self.parents[node]]
            node = self.parents[node]
        return node
    def union(self, node1, node2):
        par1 = self.find(node1)
        par2 = self.find(node2)
        if par1 != par2:
            self.parents[par1] = par2 # not parents[node1] = par2
            
    def isConnected(self, node1, node2):
        return self.find(node1) == self.find(node2)
        
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]: return board
        r = len(board)
        c = len(board[0])
        
        def node(i, j): return i*c + j # is c not r
        
        uf = UnionFound(r * c + 1)
        dummy = r*c 
        for i in range(r):
            for j in range(c):
                if board[i][j] == 'O':
                    if i==0 or j==0 or i==r-1 or j==c-1:
                        uf.union(node(i,j), dummy)
                    else:
                        if board[i-1][j] == 'O': 
                            uf.union(node(i-1,j), node(i,j))
                        if board[i+1][j] == 'O': 
                            uf.union(node(i+1,j), node(i,j))
                        if board[i][j-1] == 'O': 
                            uf.union(node(i,j-1), node(i,j))
                        if board[i][j+1] == 'O': 
                            uf.union(node(i,j+1), node(i,j))
                        
        
        for i in range(r):
            for j in range(c):
                if not uf.isConnected(dummy, node(i,j)):
                    board[i][j] = 'X'
                else:
                    board[i][j] = 'O'